#include "BinNode.hpp"

template<typename T> class BinTree {
protected:
	int _size;
	BinNodePosi(T) _root;
	/**
	 * @brief update the height of node x 
	 * 
	 * @return int 
	 */
	virtual int updateHeight(BinNodePosi(T) x);
	/**
	 * @brief Update the height of node X and its ancestors 
	 * 
	 */
	void updateHeightAbove(BinNodePosi(T) x);

public:
	BinTree(): _size(0), _root(NULL) {}
	~BinTree()
	{
		if (0 < _size)
		{
			remove(_root);
		}
	}
	int size() const {return _size;}
	bool empty() const { return !_root; }
	BinNodePosi(T) root() const { return _root; }

	BinNodePosi(T) insertAsRoot(T const &e) {
		_size = 1;
		return _root = new BinNode<T>(e);
	}
	BinNodePosi(T) insertAsLC(BinNodePosi(T) x, T const &e); // e as the left child of x
	BinNodePosi(T) insertAsRC(BinNodePosi(T) x, T const &e);
	BinNodePosi(T) attachAsLC(BinNodePosi(T) x, BinTree<T> * &t); // T accesses as the left subtree of X
	BinNodePosi(T) attachAsRC(BinNodePosi(T) x, BinTree<T> * &t);
	int remove(BinNodePosi(T) x); // Delete the subtree with x root and return the original size of the subtree
	BinTree<T>* secede(BinNodePosi(T) x); // Removes the subtree from the current tree and converts it to a separate tree  
	/**
	 * @brief  traversing binary tree
	 * 
	 * @tparam VST type of function
	 * @param visit function
	 */
	template<typename VST> 
	void travLevel(VST &visit) { if (_root) _root->travLevel(visit); }
	template<typename VST>
	void travPre(VST &visit) { if (_root) _root->travPre(visit); }
	template<typename VST>
	void travIn(VST &visit) { if (_root) _root->travIn(visit); }
	template<typename VST>
	void travPost(VST &visit) { if (_root) _root->travPost(visit); }

	/**
	 * @brief comparator 
	 * 
	 * @param t binary tree
	 * @return true 
	 * @return false 
	 */
	bool operator<( BinTree<T> const &t) const { return _root && t._root && lt(_root, t._root); }
	bool operator==(BinTree<T> const &t) const { return _root && t._root && (_root == t._root); }
};

template<typename T>
BinNodePosi(T) BinTree<T>::insertAsLC(BinNodePosi(T) x, T const &e) {
	_size++;
	x->insertAsLC(e);
	updateHeightAbove(x);
	return x->lc;
} 
template<typename T>
BinNodePosi(T) BinTree<T>::insertAsRC(BinNodePosi(T) x, T const &e) {
	_size++;
	x->insertAsRC(e);
	updateHeightAbove(x);
	return x->rc;
};
template<typename T>
BinNodePosi(T) BinTree<T>::attachAsLC(BinNodePosi(T) x, BinTree<T> * &t) {
	if(x->lc = t->_root) {
		x->lc->parent = x;
	}

	_size += t->size();
	updateHeightAbove(x);

	t->_root = NULL;
	t->_size = 0;

	release(t);
	t = NULL;

	return x;
}
template<typename T>
BinNodePosi(T) BinTree<T>::attachAsRC(BinNodePosi(T) x, BinTree<T> * &t) {
	if(x->lc = t->_root) {
		x->rc->parent = x;
	}

	_size += t->size();
	updateHeightAbove(x);

	t->_root = NULL;
	t->_size = 0;

	release(t);
	t = NULL;

	return x;
}

/**
 * @brief Postorder travsersal releases resources.
 * 
 * @tparam T 
 * @return int 
 */
template<typename T> int removeAt(BinNodePosi(T) x) {
	if(!x) return 0;
	int n = 1 + removeAt(x->lc) + removeAt(x->rc);

	release(x->data);
	release(x);
	return n;
}

template<typename T> int BinTree<T>::remove(BinNodePosi(T) x) {
	/**
	 * @brief Construct a new From Parent To object
	 * Breaks the pointer from the parent node.
	 * 
	 */
	FromParentTo(*x) = NULL;
	updateHeightAbove(x->parent);

	int n = removeAt(x);
	_size -= n;
	return n;
} 

template<class T>
BinTree<T>* BinTree<T>::secede(BinNodePosi(T) x) {
	FromParentTo(*x) = NULL;
	updateHeightAbove(x->parent);

	BinTree<T> * newTree = new BinTree<T>;
	x->parent = NULL;
	newTree->_root = x;
	newTree->_size = x->size();
	
	_size -= newTree->_size;
	return newTree;
} 

template<class T>
int BinTree<T>::updateHeight(BinNodePosi(T) x) {
	return x->height = 1 + std::max(stature(x->lc), stature(x->rc));
}

template<class T>
void BinTree<T>::updateHeightAbove(BinNodePosi(T) x) {
	while(x) {
		updateHeight(x);
		x = x->parent;
	}
}
